| 猴子跳台阶问题的三种解法（C++实现） | 您所在的位置：网站首页 › python 猴子爬山 › 猴子跳台阶问题的三种解法（C++实现） |
猴子跳台阶问题的三种解法（C++实现）
|
递推/递归问题
本人在学习递推时由于一个偶然的错误半天才解决此问题，除递推外也通过对本题的深入思考时发现了递推问题的一些特点，与此同时也深感自己代码能力的不足，写此文章希望帮助对此有需要的人。Tip：问题来自学堂在线程序设计基础
问题描述 一个顽猴在一座有N级台阶的小山上爬山跳跃，猴子上山一步可跳x级或跳y级，试求猴子上山到N级台阶有多少种不同的爬法？猴子从山脚开始跳，可认为是第0阶。 输出描述 三个正整数N,X,Y，用空格隔开。 （x if (n % x == 0) { cout if ((k % x == 0 || k % y == 0) && k != up) { f[k - 1] += 1; } if (k == up && (x != y)) f[k - 1] += 2; } for (int i = x + y; i {C_5^1}} C51或 C 5 4 {{C_5^4}} C54吗（总共5个数字，1个2或4个1），总共有5组这样的方案（ C 5 1 {{C_5^1}} C51 = C 5 4 {{C_5^4}} C54=5）；而绿圈标注的数字则是 C 4 2 {{C_4^2}} C42，总共有6组这样的方案（ C 4 2 {{C_4^2}} C42 = 6）。 根据此思路，第一种和第二章情况可以视为 C 1 1 {{C_1^1}} C11 = 1。 如果感兴趣的话可以验证其他情况，也是如此。 发现这一规律后我们可以利用双for循环，遍历X和Y可以取值的所有可能，仅计算可行方案中有多少个X多少个Y，剩下的交给排列组合函数解决即可，所有的方案数加上排列组合可能存在的所有数字即为本题答案。 以下为该思路的代码： #include using namespace std; int arrangement(int i, int j) { //计算排列问题 int all = i + j; double on = (double)all; double down = 1; int min = (i > j ? j : i); //减少运算次数 for (int k = 1; k int Count = 0; int now = 0; //猴子当前位置为第0阶 int rx = n / x; int ry = n / y; //循环次数最多只可能为n取余 //x=y时的情况 if (x == y) { if (n % x == 0) { cout for (int j = 0; j // cout cout {C_3^1}} C31 = C 3 2 {{C_3^2}} C32 = 3.方法优化和解法3 注：该方法由于需要遍历每种可能，时间复杂度为o(n²)，若延拓到有3个或多个变量会导致运行速度非常慢，所以可以对该方法进行优化。 以N=5，X=1，Y=2为例，观察下图： 但至此就可以抛开第二个方法了，因为一旦可以跳越的台阶数超过2，使用我们学过的排列组合求解问题就会变得非常困难和复杂了（因此不推荐大家使用），为了简化求解方法，依照此二叉树我们可以用分而治之的方法漂亮地解决。 递归时还是需要考虑特殊情况（X=Y），仅把实现部分的代码替换即可。递归写法的代码： #include using namespace std; int Count = 0; //可行条件 void stair(int n, int x, int y) { //递归终止条件 if (n == 0) { Count++; return; } if (n = x) stair(n - x, x, y); if (n >= y) stair(n - y, x, y); } void judge() { int n = 0, x = 0, y = 0; cin >> n >> x >> y; //不存在方案的台阶数即默认为0 if (x == y) { if (n % x == 0) { cout judge(); return 0; }当有多种跳台阶方法或有的台阶存在限定条件可以参考这篇 下楼问题 若文章有不足之处还请大家在评论区指正。 补充 如果原有问题变为了带有决策约束，如：总共n层楼梯，最开始可以走1步、2步、3步，但如果上一步走了1步，则下一步就只能走2或3步；上一步走了2步，则下一步只能走1或3步……，此类问题可以使用状态机模型结合动态规划解决，状态机的思想可以非常好的在很多具有决策性约束的问题。 |
利用二叉树可以很形象地看出问题的本质。 图中的8个ok分别对应着从N=5至当前节点的8种方法，线路上的数字表示在当前台阶向后跳的步数。由于方法2在双for循环时穷举的是补全的整棵二叉树，故可以在循环条件中加上当前台阶数是否大于总台阶数。【本文地址】